home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 181_01 / cforum.1_3 < prev    next >
Text File  |  1986-01-07  |  9KB  |  236 lines
  1. Reprinted from: Micro/Systems Journal, Volume 1. No. 3. July/August 1985
  2. -----------------------------------------------------------------
  3. Copy of back issue may be obtained for $4.50 (foreign $6) from:
  4. Subscriptions are $20/yr, $35/2yrs domestic (published bimonthly)
  5. Micro/Systems Journal
  6. Box 1192
  7. Mountainside NJ 07092
  8. -----------------------------------------------------------------
  9. Copyright 1986
  10. Micro/Systems Journal, Box 1192, Mountainside NJ 07092
  11. This software is released into the public domain for
  12.  non-commercial use only.
  13. -----------------------------------------------------------------
  14.  
  15. C FORUM  
  16.  
  17. IMPLEMENTING SETS WITH BIT OPERATIONS
  18.  
  19.      Sets with a small number of elements are easily implemented 
  20. by bit operations in most languages.  Some C compilers have a 
  21. declaration enum that allows the programmer to use sets 
  22. directly without worrying about the implementation.  
  23. Unfortunately, most C compilers don't have have the enum 
  24. construct.  In any case, the implementations I will discuss allow 
  25. more general uses then enums do, anyway.
  26.      Using bit operations we can implement sets, which in turn, 
  27. specify such operations as: union, intersection, difference, 
  28. assignment, membership, equal and size.  The ordering relation 
  29. can also be implemented, although, strictly speaking this is not 
  30. a set operation.
  31.  
  32. SMALL SETS
  33.      A simple example of the use and implementation of a set is 
  34. in the (BSD 4.2) UNIX select system call.  select() takes 
  35. parameters which represent sets of file descriptors.  Since the 
  36. number of files a process may have open is typically limited to 
  37. 20, the set of file descriptors is easily represented by a 32-bit 
  38. integer.  Each bit then, designates a file descriptor. 
  39.      For example, if the set has an integer value of 25 decimal 
  40. (or 11001 boolean), the file descriptors referred to are 4, 3 and 
  41. 0 since the bits in the 4, 3 and 0 positions are on.  In this 
  42. example, the index of the bit is exactly the value of the file 
  43. descriptor.  However this need not be the case.  What is 
  44. important is the small number of elements.
  45.      For sets like the one above, which have no more elements 
  46. than the number of bits in a single datum like an int, then we 
  47. can use the following constructs for set operations: 
  48.  
  49.   int set1, set2, set3;
  50.  
  51.   set3 = set1 | set2;    /* union */
  52.   set3 = set1 & set2;    /* intersection */
  53.   set3 = set1 & ~set2;   /* difference */
  54.  
  55.      To declare a set, define it as an int (or whatever type you 
  56. choose). I highly recommend using a typedef to make things more 
  57. readable.  Macros can also be used for the set operations 
  58. themselves.  For example: 
  59.  
  60.   #define UNION |
  61.   set3 = set1 UNION set2;
  62.  
  63.      To define a one-element set, use the macro #elt with a small 
  64. index representing the index of the element. 
  65.  
  66.   #define elt(x)        (1<<x)
  67.  
  68. #member returns 1 or 0 if an element is in the set or not.
  69.  
  70.   #define member(s,x)   (0 != \
  71.                     (s INTERSECTION elt(x)))
  72.  
  73. min_elt() returns the smallest index in a set (or -1 if the set 
  74. is empty). These examples should be enough for you to write any 
  75. other set operations you need using this representation. 
  76.  
  77. int min_elt(x)
  78. int x;
  79. {
  80.     int i;
  81.  
  82.     /* first check if set is empty */
  83.     if (x == 0) return(-1);
  84.     for (i=0;~(x&(1<<i));i++) ;
  85.     return(i);
  86. }
  87.  
  88.  
  89. BIG SETS
  90.      This is fine for sets with a small number of elements, but 
  91. what about larger sized universes?  For example, if we are 
  92. writing a device driver for a disk, we must maintain the sets of 
  93. disk cylinders that are queued to be read and written.
  94.      A list of cylinders is a prime candidate for representation 
  95. by a bit vector.  The only real difference is that such a set is 
  96. probably bigger than the number of bits in any data type on your 
  97. machine. 
  98.      For example, suppose we have 100 cylinders and our largest 
  99. data type is a 32-bit long.  Then we would need 4 longs to get at 
  100. least 100 bits for the cylinders (3*32 < 100 <= 4*32).  To get 
  101. those 100 bits, we can declare an array of longs.  #bigset is a 
  102. macro that does exactly that (listing 1).
  103.  
  104.                          LISTING 1
  105.  
  106. #define bigset(name,bits)   struct {\
  107. int number;/* of subsets */\
  108. SUBSET data[1 + bits/BITS_PER_SUBSET];\
  109.     } name = {1 + bits/BITS_PER_SUBSET};
  110.  
  111.      This macro expands to a structure declaration!  The 
  112. structure defines an array of "SUBSET"s large enough to hold the 
  113. set.  We also define the number of SUBSETs in "number", so that 
  114. we won't have to pass lengths as extra arguments into our set 
  115. routines.  SUBSET can be defined to be whatever is convenient for 
  116. you.  I always use "unsigned long" because the longer the 
  117. datatype, the faster the routines will execute.  For folks who 
  118. watch every bit, though, shorter datatypes will waste less space 
  119. (by leaving less unused bits at the end of the set array).
  120.      Finishing off #bigset, here are the macros needed.
  121.  
  122.   #define BITS_PER_BYTE   8
  123.   #define SUBSET          unsigned long
  124.   #define BITS_PER_SUBSET (BITS_PER_BYTE\
  125.                            * sizeof(SUBSET))
  126.  
  127.      Now we can declare sets for 100 cylinders to be read and 
  128. written as:
  129.  
  130.   bigset(readcyls,100);
  131.   bigset(writecyls,100);
  132.  
  133.      In order to pass these sets as parameters, we'll have to 
  134. define a type for that.  (Unfortunately, we can't use #bigset for 
  135. this because it defines a class of structures.)  We do this as 
  136. follows: 
  137.  
  138. struct bigset_param {
  139.     int number;
  140.     SUBSET data[1];
  141. };
  142.  
  143.      Most of the standard set operations (union, intersection, 
  144. assignment, etc.) look very much the same.  A single loop 
  145. performs its respective operation on an entire SUBSET at a time.  
  146. Here is the code for union.
  147.  
  148. bigset_union(s1,s2,s3)/* s1 = s2 U s3 */
  149. struct bigset_param *s1, *s2, *s3;
  150. {
  151.     int i;
  152.     for (i=0;i<s1->number;i++)
  153.         s1->data[i] = s2->data[i] UNION
  154.                       s3->data[i];
  155. }
  156.  
  157.      To use this routine, of course, you must pass the address of 
  158. the set.
  159.  
  160. bigset_print() requires an extra inner loop to print out each bit.
  161.  
  162. bigset_print(s)
  163. struct bigset_param *s;
  164. {
  165.     int i, j;
  166.     for (i=0;i<s->number;i++) {
  167. for (j=0;j<BITS_PER_SUBSET;j++) {
  168.     putchar(s->data[i]&(1<<j)?'1':'0');
  169. }
  170.     }
  171.     putchar('\n');
  172. }
  173.  
  174.      Finally, here is some code for turning on an individual bit 
  175. by its index. I chose to write it as a function only so that the 
  176. parameter passing conventions in all the bigset routines would 
  177. remain consistent.  You should be able to produce its inverse, 
  178. with a small change to the original version of min().
  179.  
  180. bigset_set(s,i)/* turn on element i in set s */
  181. struct bigset_param *s;
  182. int i;
  183. {
  184.     s->data[i/BITS_PER_SUBSET] |=
  185.                          1<<(i%BITS_PER_SUBSET);
  186. }
  187.  
  188. Finally, here is some code using these routines.
  189.  
  190. bigset(readcyls,100);
  191. bigset(readcyls,100);
  192.  
  193. main()
  194. {
  195.     /* request cylinders 1 and 10 to be read */
  196.     bigset_set(&readcyls,1);
  197.     bigset_set(&readcyls,10);
  198.     printf("cylinders to read: ");
  199.     bigset_print(&readcyls);
  200.  
  201.     /* request cylinder 4 to be written */
  202.     bigset_set(&writecyls,4);
  203.     printf("cylinders to write: ");
  204.     bigset_print(&writecyls);
  205.  
  206.     /* find out cylinders requiring action */
  207.     bigset_union(&activecyls,&readcyls,
  208.                                  &writecyls);
  209.     printf("cylinders requiring I/O: ");
  210.     bigset_print(&activecyls);
  211. }
  212.  
  213. OPTIMIZATIONS
  214.      You should now be able to finish the rest of the set 
  215. routines.  There are some obvious ways of improving the code that 
  216. you should consider if you use these routines in production code.
  217.      1) Convert bigset_set() to a macro.
  218.      2) Use pointers instead of array references in the loops.
  219.      3) Convert divisions to shifts.  Convert mods to bitwise 
  220. ands.  (This can be done only because we are working with powers 
  221. of two.)  For example, x/BITS_PER_SUBSET for BITS_PER_SUBSET == 
  222. 32 can be written x>>5 (since 5 is log of 32 base 2).
  223.  
  224. C NEWS TIDBITS
  225.      In case you are wondering what I use as a reference book on 
  226. C, it is C - A Reference Manual by Harb